1) Field of the Invention
The present invention relates to a technique of replacing an entry in case that all entries are in use in a full-associative memory device, for example, a technique preferably used, in an information processing apparatus in which a global history system or a local history system is used for predicting a branch direction of a branch instruction with reference to a past branch history held by a full-associative branch history memory section (past branch history memory section), when replacing an entry of the branch history memory section with a new entry.
2) Description of the Related Art
Up to now, a full-associative memory device having a predetermined number of entries has been provided in various kinds of devices and has been widely used.
For example, there is a technique of providing a global history register including a full-associative memory device for holding information about a past branch history for the purpose of improving prediction accuracy, in an information processing apparatus which predicts a branch destination of a branch instruction using a branch history register which holds pairs of an address of a branch instruction and an address of the predicted branch destination of its branch instruction (see patent document 1 listed below).
In a full-associative memory device having only a fixed number of entries like this global history register, it is a key to an improvement in the performance how effectively the limited entries are used, and it is important, when replacing an entry, to surely replace an unnecessary entry of the plurality of entries.
Up to now, as a method of replacing an entry in a full-associative memory device, we have had a round robin method by which an entry registered earliest is replaced and a least-recently-used (LRU) method by which en entry least recently used since it was accessed is replaced.
Furthermore, we have other replacing methods including techniques of selecting an entry to be replaced on the basis of a success rate (number of coincidences) in branch prediction, in the technical field related to branch prediction for a branch instruction (see patent documents 2 and 3 listed below).
However, in the round robin method described above, it is not taken into consideration at all to use entries effectively, and an entry is erased without reservation if it was registered earliest even if it is very effective for branch prediction or it is in use, whereby it is difficult to say that the method is an effective replacing method.
Furthermore, in the LRU method described above, an entry least recently used since it was accessed is selected as an unnecessary entry which is an object of replacement, and therefore particularly in a global history register (see patent document 1 listed above) or the like which expects a history will be repeated and provides an expectation value from its periodicity, an entry least recently used since it was accessed is not always an unnecessary entry due to its characteristic.
In other words, it is desirable to avoid, from the viewpoint of the characteristic of the global history register, that the entry about such a long interval branch instruction as to appear with a low frequency but at a fixed interval is assumed to be an entry which is an object of replacement, if possible. However, with the LRU method, the possibility of assuming the entry about an instruction appearing with a low frequency to be an entry, which is an object of replacement, becomes high, so it is also difficult to say that the LRU method is an effective method.
In addition, with the LRU method, it is necessary to separately hold information about an accessed history, which requires a resource cost for holding such information, and therefore the limited resources of the full-associative memory device are not used effectively.
Furthermore, with techniques of using a success rate in branch prediction, etc. disclosed in patent documents 2 and 3 described above, it is necessary, like the LRU method, to separately hold information about the success rate, etc., thereby increasing the resource cost.
[Patent Document 1] Japanese Patent Laid-Open (Kokai) No. 2004-38323
[Patent Document 2] Japanese Patent Laid-Open (Kokai) No. 2002-278752
[Patent Document 3] Japanese Patent Laid-Open (Kokai) No. HEI 6-67880